Search for: All records

Suffix sorting stands at the core of the most efficient solutions for indexed pattern matching: the suffix tree, the suffix array, compressed indexes based on the Burrows-Wheeler transform, and so on. In [Gagie, Manzini, Sirén, TCS 2017] this concept was extended to labeled graphs, obtaining the rich class of Wheeler graphs. This work opened a very fruitful line of research, ultimately generating results able to bridge the fields of compressed data structures, graph theory, and regular language theory. In a Wheeler graph, nodes are sorted according to the alphabetic order of their incoming labels, propagating this order through pairs of equally-labeled edges. This apparently-simple definition makes it possible to solve on Wheeler graphs problems (including, but not limited to: compression, subpath queries, NFA equivalence, determinization, minimization) that on general labeled graphs are extremely hard to solve, and induces a rich structure in the class of regular languages (Wheeler languages) recognized by automata whose state transition is a Wheeler graph. The goal of this survey is to provide a summary of (and intuitions behind) the results on Wheeler graphs that appeared in the literature since their introduction, in addition to a discussion of interesting problems that are still open in the field. 

For a length n text over an alphabet of size σ, we can encode the suffix tree data structure in 𝒪(nlog σ) bits of space. It supports suffix array (SA), inverse suffix array (ISA), and longest common extension (LCE) queries in 𝒪(log^ε_σ n) time, which enables efficient pattern matching; here ε > 0 is an arbitrarily small constant. Further improvements are possible for LCE queries, where 𝒪(1) time queries can be achieved using an index of space 𝒪(nlog σ) bits. However, compactly indexing a two-dimensional text (i.e., an n× n matrix) has been a major open problem. We show progress in this direction by first presenting an 𝒪(n²log σ)-bit structure supporting LCE queries in near 𝒪((log_σ n)^{2/3}) time. We then present an 𝒪(n²log σ + n²log log n)-bit structure supporting ISA queries in near 𝒪(log n ⋅ (log_σ n)^{2/3}) time. Within a similar space, achieving SA queries in poly-logarithmic (even strongly sub-linear) time is a significant challenge. However, our 𝒪(n²log σ + n²log log n)-bit structure can support SA queries in 𝒪(n²/(σ log n)^c) time, where c is an arbitrarily large constant, which enables pattern matching in time faster than what is possible without preprocessing. We then design a repetition-aware data structure. The δ_2D compressibility measure for two-dimensional texts was recently introduced by Carfagna and Manzini [SPIRE 2023]. The measure ranges from 1 to n², with smaller δ_2D indicating a highly compressible two-dimensional text. The current data structure utilizing δ_2D allows only element access. We obtain the first structure based on δ_2D for LCE queries. It takes 𝒪^{~}(n^{5/3} + n^{8/5}δ_2D^{1/5}) space and answers queries in 𝒪(log n) time. 

We study the problem of indexing a text T[1..n] to support pattern matching with wildcards. The input of a query is a pattern P[1..m] containing h ∈ [0, k] wildcard (a.k.a. don't care) characters and the output is the set of occurrences of P in T (i.e., starting positions of substrings of T that matches P), where k = o(log n) is fixed at index construction. A classic solution by Cole et al. [STOC 2004] provides an index with space complexity O(n ⋅ (clog n)^k/k!)) and query time O(m+2^h log log n+occ), where c > 1 is a constant, and occ denotes the number of occurrences of P in T. We introduce a new data structure that significantly reduces space usage for highly repetitive texts while maintaining efficient query processing. Its space (in words) and query time are as follows: O(δ log (n/δ)⋅ c^k (1+(log^k (δ log n))/k!)) and O((m+2^h +occ)log n)) The parameter δ, known as substring complexity, is a recently introduced measure of repetitiveness that serves as a unifying and lower-bounding metric for several popular measures, including the number of phrases in the LZ77 factorization (denoted by z) and the number of runs in the Burrows-Wheeler Transform (denoted by r). Moreover, O(δ log (n/δ)) represents the optimal space required to encode the data in terms of n and δ, helping us see how close our space is to the minimum required. In another trade-off, we match the query time of Cole et al.’s index using O(n+δ log (n/δ) ⋅ (clogδ)^{k+ε}/k!) space, where ε > 0 is an arbitrarily small constant. We also demonstrate how these techniques can be applied to a more general indexing problem, where the query pattern includes k-gaps (a gap can be interpreted as a contiguous sequence of wildcard characters). 

We revisit the following version of the Gapped String Indexing problem, where the goal is to preprocess a text T[1..n] to enable efficient reporting of all occ occurrences of a gapped pattern P=P1[α..β]P2 in T. An occurrence of P in T is defined as a pair (i,j) where substrings T[i..i+|P1|) and T[j..j+|P2|) match P1 and P2, respectively, with a gap j−(i+|P1|) lying within the interval [α..β]. This problem has significant applications in computational biology and text mining. A hardness result on this problem suggests that any index with polylogarithmic query time must occupy near quadratic space. In a recent study [STACS 2024], Bille et al. presented a sub-quadratic space index using space O˜(n2−δ/3), where 0≤δ≤1 is a parameter fixed at the time of index construction. Its query time is O˜(|P1|+|P2|+nδ·(1+occ)), which is sub-linear per occurrence when δ<1. We show how to achieve a gap-sensitive query time of O˜(|P1|+|P2|+nδ·(1+occ1−δ)+∑g∈[α..β]occg·gδ) using the same space, where occg denotes the number of occurrences with gap g. This is faster when there are many occurrences with small gaps. 

We use a bulk acoustic wave resonator to demonstrate coherent control of the excited orbital states in a diamond nitrogen-vacancy ( $\text{N}$ $\mathrm{V}$) center at cryogenic temperature. Coherent quantum control is an essential tool for understanding and mitigating decoherence. Moreover, characterizing and controlling orbital states is a central challenge for quantum networking, where optical coherence is tied to orbital coherence. We study resonant multiphonon orbital Rabi oscillations in both the frequency and time domain, extracting the strength of the orbital-phonon interactions and the coherence of the acoustically driven orbital states. We reach the strong-driving limit, where the physics is dominated by the coupling induced by the acoustic waves. We find agreement between our measurements, quantum master-equation simulations, and a Landau-Zener transition model in the strong-driving limit. Using perturbation theory, we derive an expression for the orbital Rabi frequency versus the acoustic drive strength that is nonperturbative in the drive strength and agrees well with our measurements for all acoustic powers. Motivated by continuous-wave spin-resonance-based decoherence protection schemes, we model the orbital decoherence and find good agreement between our model and our measured few-to-several-nanoseconds orbital decoherence times. We discuss the outlook for orbital decoherence protection. Published by the American Physical Society2024 

Abstract The radiation mechanism underlying the prompt emission remains unresolved and can be resolved using a systematic and uniform time-resolved spectro-polarimetric study. In this paper, we investigated the spectral, temporal, and polarimetric characteristics of five bright gamma-ray bursts (GRBs) using archival data from AstroSat CZTI, Swift Burst Alert Telescope, and Fermi/GBM. These bright GRBs were detected by CZTI in its first year of operation, and their average polarization characteristics have been published in Chattopadhyay et al. In the present work, we examined the time-resolved (in 100–600 keV) and energy-resolved polarization measurements of these GRBs with an improved polarimetric technique such as increasing the effective area and bandwidth (by using data from low-gain pixels), using an improved event selection logic to reduce noise in the double events and extend the spectral bandwidth. In addition, we also separately carried out detailed time-resolved spectral analyses of these GRBs using empirical and physical synchrotron models. By these improved time-resolved and energy-resolved spectral and polarimetric studies (not fully coupled spectro-polarimetric fitting), we could pin down the elusive prompt emission mechanism of these GRBs. Our spectro-polarimetric analysis reveals that GRB 160623A, GRB 160703A, and GRB 160821A have Poynting flux-dominated jets. On the other hand, GRB 160325A and GRB 160802A have baryonic-dominated jets with mild magnetization. Furthermore, we observe a rapid change in polarization angle by ∼90° within the main pulse of very bright GRB 160821A, consistent with our previous results. Our study suggests that the jet composition of GRBs may exhibit a wide range of magnetization, which can be revealed by utilizing spectro-polarimetric investigations of the bright GRBs.